IP-Forwarding is the process in which an Internet router uses the IP destination address of an incoming packet to search a routing-table using a longest-matching prefix search method in order to determine the next router, i.e. next hop, to which the packet shall be forwarded. If no matching prefix is found then the packet is routed according to a so-called “default route”.
Two developments can be observed in the routing-table lookup function in Internet routers: First, high search rates for increasing link speeds (OC-192, OC-768, etc.) force the lookup function to use fast but expensive memory such as embedded DRAM and SRAM, having only limited storage capacity. Second, exponentially growing routing-tables force the lookup function to support very large routing-tables. These two developments drive a renewed interest in the use of caches for routing-table lookups.
EP 1122927 is directed to a route lookup engine for determining a next hop. That route lookup engine receives a lookup key and performs a multi-bit trie search with prefix expansion and capture of a variable stride trie.
EP 1011231 describes a method an apparatus providing for router redundancy of non Internet protocols using the virtual router redundancy protocol.
U.S. Ser. No. 20020,091,856A1 describes a default route coding method. A multilevel lookup table includes a plurality of search levels with each search level including a plurality of subtrees, each subtree representing a plurality of nodes. A search of the multilevel lookup table for an entry corresponding to a search key results in a value stored in an entry associated with the node in a subtree. A default value is associated with the root of the subtree. Multiple entries for the subtree can store the default value. To minimize route update time, the default value associated with the subtree is stored in a single location. Instead of storing the default value in multiple entries, each entry stores a use default indicator to indicate that the default value stored in the single location is to be used. To further reduce the number of locations to modify to update the default route, the single location can store an inherit indicator to indicate that the default value for the subtree is inherited from another subtree.
Within enterprise networks, a significant portion of the traffic is likely to be routed according to the default route. The default route, however, does not relate to a specific prefix and is therefore not cached. Consequently, packets that are routed according to the default route, will always result in cache misses.